P3327 [SDOI2015]约数个数和
首先可以得出 d ( i j ) = ∑ x ∣ i ∑ y ∣ j ( g c d ( x , y ) = 1 ) d(ij)=\sum\limits_{x|i}\sum\limits_{y|j}(gcd(x,y)=1) d ( ij ) = x ∣ i ∑ y ∣ j ∑ ( g c d ( x , y ) = 1 )
证明
首先令 i = p 1 α 1 p 2 α 2 . . . p k α k , j = p 1 β 1 p 2 β 2 . . . p k β k i=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k},j=p_1^{\beta_1}p_2^{\beta_2}...p_k^{\beta_k} i = p 1 α 1 p 2 α 2 ... p k α k , j = p 1 β 1 p 2 β 2 ... p k β k
那么 i j = p 1 α 1 + β 1 p 2 α 2 + β 2 . . . p k α k + β k ij=p_1^{\alpha_1+\beta_1}p_2^{\alpha_2+\beta_2}...p_k^{\alpha_k+\beta_k} ij = p 1 α 1 + β 1 p 2 α 2 + β 2 ... p k α k + β k
可以得出约数个数为 ( α 1 + β 2 + 1 ) ( α 2 + β 2 + 1 ) . . . ( α k + β k + 1 ) (\alpha_1+\beta_2+1)(\alpha_2+\beta_2+1)...(\alpha_k+\beta_k+1) ( α 1 + β 2 + 1 ) ( α 2 + β 2 + 1 ) ... ( α k + β k + 1 )
由 x ∣ i , y ∣ j , g c d ( x , y ) = 1 x|i,y|j,gcd(x,y)=1 x ∣ i , y ∣ j , g c d ( x , y ) = 1
可知对于每一个 p i p_i p i
x , y x,y x , y ( p i 0 , p i 0 ) , ( p i 1 , p i 0 ) . . . ( p i α i , p i 0 ) , ( p i 0 , p i 1 ) . . . ( p i 0 , p i β i ) (p_i^0,p_i^0),(p_i^1,p_i^0)...(p_i^{\alpha^i},p_i^0),(p_i^0,p_i^1)...(p_i^0,p_i^{\beta^i}) ( p i 0 , p i 0 ) , ( p i 1 , p i 0 ) ... ( p i α i , p i 0 ) , ( p i 0 , p i 1 ) ... ( p i 0 , p i β i )
一共是 α i + β i + 1 \alpha^i+\beta^i+1 α i + β i + 1
那么加起来就等于约数个数了
证毕
接下来才是重头戏
∑ i = 1 n ∑ j = 1 m d ( i j ) = ∑ i = 1 n ∑ j = 1 m ∑ x ∣ i ∑ y ∣ j ( g c d ( x , y ) = 1 ) \sum\limits_{i=1}^n\sum\limits_{j=1}^md(ij)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x|i}\sum\limits_{y|j}(gcd(x,y)=1)
i = 1 ∑ n j = 1 ∑ m d ( ij ) = i = 1 ∑ n j = 1 ∑ m x ∣ i ∑ y ∣ j ∑ ( g c d ( x , y ) = 1 )
令 F k = ∑ i = 1 n ∑ j = 1 m ∑ x ∣ i ∑ y ∣ j ( k ∣ g c d ( x , y ) ) , f k = ∑ i = 1 n ∑ j = 1 m ∑ x ∣ i ∑ y ∣ j ( g c d ( x , y ) = k ) F_k=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x|i}\sum\limits_{y|j}(k|gcd(x,y)),f_k=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x|i}\sum\limits_{y|j}(gcd(x,y)=k) F k = i = 1 ∑ n j = 1 ∑ m x ∣ i ∑ y ∣ j ∑ ( k ∣ g c d ( x , y )) , f k = i = 1 ∑ n j = 1 ∑ m x ∣ i ∑ y ∣ j ∑ ( g c d ( x , y ) = k )
则 F k = ∑ k ∣ d f d F_k=\sum\limits_{k|d}f_d F k = k ∣ d ∑ f d
由莫比乌斯反演可以得出 f k = ∑ n ∣ d μ ( d n ) F d f_k=\sum\limits_{n|d}\mu(\frac{d}{n})F_d f k = n ∣ d ∑ μ ( n d ) F d
但是到这依然不好求,考虑优化一下 F k F_k F k
F k = ∑ i = 1 n ∑ j = 1 m ∑ x ∣ i ∑ y ∣ j ( k ∣ g c d ( x , y ) ) F_k=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x|i}\sum\limits_{y|j}(k|gcd(x,y))
F k = i = 1 ∑ n j = 1 ∑ m x ∣ i ∑ y ∣ j ∑ ( k ∣ g c d ( x , y ))
交换一下循环顺序
F k = ∑ x = 1 n ∑ y = 1 m ? F_k=\sum\limits_{x=1}^n\sum\limits_{y=1}^m?
F k = x = 1 ∑ n y = 1 ∑ m ?
可以得出外面两层循环的范围,那么里面两层呢?可以看出最里面的值与 i , j i,j i , j ( n , m ) (n,m) ( n , m ) ( i , j ) (i,j) ( i , j )
F k = ∑ x = 1 n ∑ y = 1 m ⌊ n x ⌋ ⌊ m y ⌋ ( k ∣ g c d ( x , y ) ) F_k=\sum\limits_{x=1}^n\sum\limits_{y=1}^m\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor (k|gcd(x,y))
F k = x = 1 ∑ n y = 1 ∑ m ⌊ x n ⌋ ⌊ y m ⌋ ( k ∣ g c d ( x , y ))
令 x ‘ = x k , y ‘ = y k , n ‘ = n k , m ‘ = m k x`=\frac{x}{k},y`=\frac{y}{k},n`=\frac{n}{k},m`=\frac{m}{k} x ‘ = k x , y ‘ = k y , n ‘ = k n , m ‘ = k m
F k = ∑ x ‘ = 1 n ‘ ∑ y ‘ = 1 m ‘ ⌊ n ‘ x ‘ ⌋ ⌊ m ‘ y ‘ ⌋ F_k=\sum\limits_{x`=1}^{n`}\sum\limits_{y`=1}^{m`}\lfloor\frac{n`}{x`}\rfloor\lfloor\frac{m`}{y`}\rfloor
F k = x ‘ = 1 ∑ n ‘ y ‘ = 1 ∑ m ‘ ⌊ x ‘ n ‘ ⌋ ⌊ y ‘ m ‘ ⌋
尝试将它展开,可以得到类似于 a 1 b 1 + a 1 b 2 + . . . + a 1 b n + a 2 b 1 + . . . + a 2 b n + . . . a_1 b_1+a_1 b_2+...+a_1 b_n+a_2 b_1+...+a_2 b_n+... a 1 b 1 + a 1 b 2 + ... + a 1 b n + a 2 b 1 + ... + a 2 b n + ... ( a 1 + a 2 + . . . + a n ) ( b 1 + b 2 + . . . + b n ) (a_1+a_2+...+a_n)(b_1+b_2+...+b_n) ( a 1 + a 2 + ... + a n ) ( b 1 + b 2 + ... + b n )
那么 F k = ( ∑ x ‘ = 1 n ‘ ⌊ n ‘ x ‘ ⌋ ) ( ∑ y ‘ = 1 m ‘ ⌊ m ‘ y ‘ ⌋ ) F_k=(\sum\limits_{x`=1}^{n`}\lfloor\frac{n`}{x`}\rfloor)(\sum\limits_{y`=1}^{m`}\lfloor\frac{m`}{y`}\rfloor) F k = ( x ‘ = 1 ∑ n ‘ ⌊ x ‘ n ‘ ⌋) ( y ‘ = 1 ∑ m ‘ ⌊ y ‘ m ‘ ⌋)
不妨令 h ( x ) = ∑ i = 1 x ⌊ x i ⌋ h(x)=\sum\limits_{i=1}^x\lfloor\frac{x}{i}\rfloor h ( x ) = i = 1 ∑ x ⌊ i x ⌋
F k = h ( n k ) h ( m k ) F_k=h(\frac{n}{k})h(\frac{m}{k})
F k = h ( k n ) h ( k m )
再代回上面的式子
f k = ∑ k ∣ d μ ( d k ) h ( n d ) h ( m d ) f_k=\sum\limits_{k|d}\mu(\frac{d}{k})h(\frac{n}{d})h(\frac{m}{d})
f k = k ∣ d ∑ μ ( k d ) h ( d n ) h ( d m )
到这就很明显可以用整除分块预处理出来所有的 h ( x ) h(x) h ( x )
代码
#include<iostream> #include<cstdio> using namespace std; const int N = 5e4 + 5; typedef long long ll; int prime[N], mu[N], sum[N], h[N], tot; bool st[N]; int g(int k, int x) { return k / (k / x); } void init() { mu[1] = 1; for (int i = 2; i < N; i++) { if (!st[i]) prime[++tot] = i, mu[i] = -1; for (int j = 1; prime[j] * i < N; j++) { st[i * prime[j]] = true; if (i % prime[j] == 0) break; mu[i * prime[j]] = -mu[i]; } } for (int i = 1; i < N; i++) sum[i] = sum[i - 1] + mu[i]; for (int i = 1; i < N; i++) { for (int l = 1, r; l <= i; l = r + 1) { r = min(i, g(i, l)); h[i] += (r - l + 1) * (i / l); } } } int main() { init(); int T; scanf("%d", &T); while (T--) { int n, m; scanf("%d%d", &n, &m); int k = min(n, m); ll ans = 0; for (int l = 1, r; l <= k; l = r + 1) { r = min(k, min(g(n, l), g(m, l))); ans += (ll)(sum[r] - sum[l - 1]) * h[n / l] * h[m / l]; } printf("%lld\n", ans); } return 0; }
